【基本情報技術者試験平成27年春期午前】問題・解説・解答

[TOP] [午前分野別] [午後分野別] [キーワード索引] [令和元年秋午前] [令和元年秋午後]

平成27年春期基本情報技術者午前問06

問06　　 ２分探索法の計算量

　整列された n 個のデータの中から、求める要素を２分探索法で探索する。この処理の計算量のオーダを表す式はどれか。

ア　log n　　　　　　　イ　n　　　　　　　ウ　n ²　　　　　　　エ　n log n

解説

　２分探索法は、ソートされたデータの中央のデータと探索するデータを比較し、前方にあるか後方にあるかを判断する。探索するデータが、前方にあるの場合は、次に前半のデータの中央のデータと比較する。この操作を繰り返すことによって、データを探索する。

　要素数が n 個の場合に２分探索法を使った場合の比較回数は，次の式で求めることができる。

平均比較回数：(log n)回
最大比較回数：(log n)＋１回

【平成21年春問07 IT パスポート類題】